Texpress : optimiser et configurer le moteur de base de données

Texpress utilise un Système de codage superposé à deux niveaux pour la recherche de correspondances partielles comme principal mécanisme d'indexation. Nous explorons ici ce que nous entendons par Schéma de codage superposé et examinons les variables qui affectent la configuration optimale.

Le schéma est composé de deux parties : la première est un schéma de codage, et la seconde est le mécanisme de superposition. Pour expliquer le fonctionnement de ces stratégies, un exemple concret sera utilisé. Pour l'exemple, nous supposerons que nous avons un enregistrement Personnes / Organisations simple avec les données suivantes :

Nom du champ	Valeur
Prénom	Boris
Nom	Badenov
Ville	FrostBite Falls
État	Minnesota

Schéma de codage

La première partie de l'algorithme d'indexation consiste à coder chacune des valeurs du champ en une chaîne de bits, c'est-à-dire une séquence de bits zéro et un. Deux variables sont utilisées lors de l'encodage d'une valeur. La première est k, qui est le nombre de 1 dont nous avons besoin pour la valeur et le second est b, qui est la longueur de la chaîne de bits. Les variables b et k sont les deux premières entrées dans la configuration du mécanisme d'indexation.

Pour coder une valeur, nous utilisons un générateur de nombres pseudo-aléatoires. Nous devons appeler le générateur k fois et la valeur résultante doit être comprise entre 0 et b - 1. Pour chaque nombre généré, nous convertissons la position du bit en un 1. La caractéristique importante d'un générateur de nombres pseudo-aléatoires est que si nous fournissons les mêmes entrées (c'est-à-dire les mêmes k, b et valeur), les mêmes k nombres seront générés, donc les mêmes entrées produiront toujours les mêmes sorties. Supposons que nous utilisions k=2 et b=15 pour coder notre enregistrement de test. La table ci-dessous présente des exemples de chaînes de bits générées pour les valeurs données b et k :

Valeur	Positions des bits	Chaîne de bits
Boris	3, 10	00010 00000 10000
Badenov	1, 4	01001 00000 00000
FrostBite	3, 7	00010 00100 00000
Falls	8, 14	00000 00010 00001
Minnesota	4, 9	00001 00001 00000

Remarquez comment les deux mots du champ Ville sont codés séparément. C'est ce codage distinct qui permet de prendre en charge la recherche par mot, c'est-à-dire la recherche où un seul mot est spécifié. Le générateur de nombres pseudo-aléatoires utilisé par Texpress requiert également une autre entrée, le numéro de colonne de la valeur à indexer. La raison de cette entrée est que le même mot dans différentes colonnes devrait donner lieu à des chaînes de bits différentes. Sinon une recherche sur ce mot le trouverait dans toutes les colonnes (c'est ainsi que la fonction Rechercher aussi est mise en œuvre, où chaque colonne Rechercher aussi utilise le même numéro de colonne, celui de la colonne d'origine).

Schéma superposé

Une fois que toutes les chaînes de bits sont générées, elles sont combinées par OU pour produire la chaîne de bits finale. La chaîne de bits est appelée descripteur d'enregistrement, car elle contient une version codée des données de l'enregistrement, en d'autres termes, elle décrit le contenu de l'enregistrement sous la forme d'une chaîne de bits. En utilisant notre exemple, le descripteur d'enregistrement résultant serait :

00010 00000 10000	OU
01001 00000 00000
00010 00100 00000
00000 00010 00001
00001 00001 00000
01011 00111 10001

Fausses correspondances

Le système d'indexation utilisé par Texpress peut indiquer qu'un enregistrement correspond à une requête alors que ce n'est pas le cas. Ces fausses correspondances sont dues au mécanisme d'encodage utilisé. Lorsqu'une requête est effectuée, le terme de la requête est codé en une chaîne de bits comme décrit ci-dessus. Le descripteur d'enregistrement résultant, généralement connu sous le nom de descripteur de requête, est soumis à une opération ET avec chaque descripteur d'enregistrement et, lorsque le descripteur résultant est identique au descripteur de requête, l'enregistrement correspond (c'est-à-dire que le descripteur d'enregistrement a un 1 dans chaque position où le descripteur d'interrogation a un 1). En utilisant notre exemple ci-dessus, supposons que nous recherchons le terme Boris. Nous codons le terme et le comparons au descripteur de l'enregistrement :

00010 00000 10000	ET	(Boris descripteur de requête)
01011 00111 10001		(descripteur d'enregistrement)
00010 00000 10000		(Descripteur résultant)

Étant donné que le descripteur résultant est le même que le descripteur de la requête, l'enregistrement est marqué comme une correspondance. Considérons maintenant la recherche de Natasha. Afin de démontrer une fausse correspondance, supposons que Natasha est codé comme suit :

Valeur	Positions des bits	Chaîne de bits
Natasha	7, 9	00000 00101 00000

Lorsque nous effectuons notre recherche, nous obtenons :

00000 00101 00000	ET	(Natasha descripteur de requête)
01011 00111 10001		(descripteur d'enregistrement)
00000 00101 00000		(Descripteur résultant)

Comme vous pouvez le constater, le descripteur de requête est le même que le descripteur résultant. Il semble donc que les enregistrements correspondent, sauf que l'enregistrement du descripteur 01011 00111 10001 ne contient pas Natasha. C'est ce qu'on appelle une fausse correspondance. Afin de « masquer » les fausses correspondances aux utilisateurs, Texpress vérifie chaque enregistrement avant de l'afficher pour confirmer qu'elle contient bien le ou les termes de requête spécifiés. Si ce n'est pas le cas, l’enregistrement est retiré de l'ensemble des correspondances.

La raison de ces fausses correspondances est qu'une combinaison des bits définis pour une série de termes dans un enregistrement fait apparaître des 1 dans les mêmes positions que pour un seul terme. En utilisant notre exemple, vous pouvez voir que Frostbite génère le bit sept et que Minnesota génère le bit neuf, qui se trouvent correspondre aux bits générés par Natasha. Afin d'assurer une requête précise, nous devons réduire au minimum le nombre de fausses correspondances.

Calcul de k et b

Maintenant que nous avons vu comment fonctionne le schéma de codage superposé, c'est-à-dire en traduisant le contenu d'un enregistrement en un descripteur d'enregistrement, nous devons étudier comment calculer k (nombre de bits à définir pour 1 par terme) et b (longueur de la chaîne de bits). La première variable que nous allons examiner est k. Afin de calculer k, nous devons introduire deux nouvelles variables :

d

La densité de bits est le rapport entre le nombre de bits 1 définis et la longueur du descripteur. La valeur est exprimée en pourcentage. Par exemple, une densité binaire de 25 % indique qu'un bit sur quatre sera égal à 1, les trois autres étant des 0, lorsqu'on fait la moyenne sur l'ensemble du descripteur d'enregistrement. Si nous utilisons notre exemple de descripteur d'enregistrement de 01011 00111 10001, il y a huit bits 1 sur un total de 15 bits, ce qui donne une densité binaire de 8/15 ou 53 %. Texpress utilise une valeur de densité binaire par défaut de 25 %.

f

La probabilité de fausse correspondance est le nombre de descripteurs d'enregistrements que nous devons examiner pour obtenir une fausse correspondance. Par exemple, une valeur de 1024 indique que nous nous attendons à avoir une fausse correspondance pour chaque 1024 descripteurs d'enregistrement vérifiés lors de la requête. Grâce à cette variable, nous pouvons configurer le système pour qu'il fournisse un niveau « acceptable » de fausses correspondances. Texpress utilise la valeur 1024 pour la probabilité de fausse correspondance pour les descripteurs d'enregistrements.

Le nombre de bits que nous devons définir pour un terme est lié à la fois à la probabilité de fausse correspondance et à la densité de bits. Si nous utilisons une densité de bits de 25 %, un bit sur quatre est défini sur 1 dans notre descripteur d'enregistrement. Cela implique que la probabilité qu'un bit donné soit un 1 est de 1/4. Si k est défini sur 1, un bit est donc généré par terme, la probabilité que le bit soit déjà défini est de 1/4. Si deux bits sont activés (k=2), la probabilité que les deux bits soient définis est de 1/4 * 1/4 = 1/16. La table ci-dessous donne plus de détails :

k	Probabilité que tous les bits soient définis sur un	Valeur
1	1/4	1/4
2	1/4 * 1/4	1/16
3	1/4 * 1/4 * 1/4	1/64
4	1/4 * 1/4 * 1/4 * 1/4	1/256
5	1/4 * 1/4 * 1/4 * 1/4 * 1/4	1/1024
6	1/4 * 1/4 * 1/4 * 1/4 * 1/4 * 1/4	1/4096

Si la probabilité de fausse correspondance est fixée à 1024 (comme utilisé par Texpress), vous pouvez voir dans la table ci-dessus que nous devons fixer k à 5. La raison pour laquelle la valeur cinq est sélectionnée est que, pour obtenir une fausse correspondance, tous les bits du terme dont la requête est faite doivent être définis sur un, mais ne doivent pas contenir le terme. Ainsi, si k est égal à cinq, nous avons une chance sur 1024 qu'un descripteur d'enregistrement ne corresponde pas correctement. Si nous diminuons la densité de bits à, disons, 12,5 % ou un bit sur huit, une valeur de quatre pour k est suffisante, comme le montre la table ci-dessous :

k	Probabilité que tous les bits soient définis sur un	Valeur
1	1/8	1/8
2	1/8 * 1/8	1/64
3	1/8 * 1/8 * 1/8	1/512
4	1/8 * 1/8 * 1/8 * 1/8	1/4096

Il est facile de voir que si nous diminuons la densité de bits (d), nous diminuons également la valeur de k. Nous pouvons exprimer la relation entre k, f et d comme suit :

f = (100 / d)k

Avec un peu de calcul, nous pouvons isoler k de la formule ci-dessus, ce qui donne :

k = log(f) / log(100 / d)

Maintenant que k est calculé, nous pouvons l'utiliser pour déterminer la valeur de b (la longueur de la chaîne de bits). Nous devons introduire une nouvelle variable afin de calculer b :

i

Le nombre d'atomes indexés par enregistrement définit le nombre de valeurs à encoder dans le descripteur d'enregistrement. Dans notre exemple, la valeur de i est de cinq car nous avons cinq termes encodés dans le descripteur de l'enregistrement (Boris, Badenov, Frostbite, Falls, Minnesota). La valeur de i dépend des données contenues dans un enregistrement, qui peuvent varier d'un enregistrement à l'autre. Nous reviendrons plus tard sur i lorsque nous verrons comment déterminer une valeur appropriée.

En utilisant la valeur de i, nous pouvons calculer la valeur de b. En utilisant une approche simpliste, nous pourrions prendre la valeur de k (bits à définir par terme) et la multiplier par i (nombre de termes) pour obtenir le nombre de bits définis sur 1. Si nous supposons que d (densité de bits) est de 25 %, nous devons multiplier le nombre de 1 définis par quatre pour obtenir la valeur de b. Exprimé sous forme de formule, on obtient (i * k * (100/d)). En utilisant notre exemple, nous aurions :

5 * 5 * (100 / 25) = 100 bits

Ainsi, pour notre exemple d'enregistrement, nous aurions la configuration suivante :

Variable	Description	Valeur
f	Probabilité de fausse correspondance	1024
d	Densité de bits	25 %
i	Termes indexés par enregistrement	5
k	Bits définis par terme	5
b	Longueur de la chaîne de bits (en bits)	100

En réalité, la formule utilisée pour calculer b est un peu simpliste. Elle est utile en tant qu'approximation, mais elle n'est pas totalement exacte. Lorsque nous construisons le descripteur d'un enregistrement, nous utilisons le générateur de nombres pseudo-aléatoires pour calculer k bits par terme. Si nous avons i termes, nous appelons le générateur de nombres pseudo-aléatoires i fois, une fois pour chaque terme. Chaque terme définira les bits k/b. Ainsi, pour chaque terme, la probabilité qu'un bit soit encore 0 est (1 - k/b), donc pour les termes i la probabilité qu'un bit soit encore 0 est (1 - k/b)ⁱ. De ce fait la probabilité qu'un bit soit 1 doit être (1 - (1 - k/b)ⁱ). Nous savons également que la probabilité qu'un bit soit 1 doit être (d/100), c'est-à-dire le nombre de bits 1 sur la base de la densité binaire. On se retrouve donc avec :

1 - (1 - k/b)i = d / 100

Maintenant, avec un peu de calcul, nous pouvons isoler b de la formule ci-dessus, ce qui donne :

b = k / (1 - exp(log((100 - d) / 100) / i))

En utilisant la formule ci-dessus pour b avec notre exemple d’enregistrement, nous obtenons une valeur de 90 bits au lieu des 100 calculés par la méthode simpliste. Si vous n'avez pas compris la façon dont b était calculé, ce n'est pas important, sauf pour comprendre que Texpress utilise cette dernière formule pour déterminer b. Maintenant que les concepts clés sont en place et que nous avons examiné les variables utilisées pour calculer le nombre de bits à définir par terme (k) et la longueur de la chaîne de bits (b), nous devons examiner ce que nous entendons par Deux niveaux lorsque nous parlons d'un Schéma de codage à deux niveaux pour la récupération des correspondances partielles.

Comme vous pouvez l'imaginer, un système d'indexation à deux niveaux doit comporter deux parties, et c'est effectivement le cas. Heureusement, les deux parties sont très similaires et utilisent la théorie couverte dans la dernière section. Le premier niveau est le niveau du descripteur de segment et le second est le niveau du descripteur d'enregistrement :

Descripteur de segment

Un descripteur de segment est une chaîne de bits qui code des informations pour un nombre fixe d'enregistrements. Il utilise la théorie présentée ci-dessus, sauf qu'un descripteur de segment simple décrit un groupe d'enregistrements plutôt qu'un enregistrement unique. Le nombre d'enregistrements dans un segment fait partie de la configuration du système et est connu sous le nom de Nr. Une valeur typique pour Nr est d'environ 10. Les descripteurs de segment sont stockés de manière séquentielle dans le fichier seg sous le répertoire de la base de données, c'est-à-dire que le premier descripteur de segment encode les premiers Nr enregistrements, le second les Nr enregistrements suivants et ainsi de suite.

Descripteur d'enregistrement

Le niveau Descripteurs d'enregistrement contient un descripteur d'enregistrement par enregistrement. Les descripteurs d'enregistrements sont regroupés en lots de Nr. Les lots sont stockés les uns après les autres dans le fichier rec sous le répertoire de la base de données.

La table ci-dessous montre la relation entre les descripteurs de segments et les descripteurs d'enregistrements où N_r est 4 :

Descripteur de segment 1	Descripteur d'enregistrement 1
	Descripteur d'enregistrement 2
	Descripteur d'enregistrement 3
	Descripteur d'enregistrement 4
Descripteur de segment 2	Descripteur d'enregistrement 5
	Descripteur d'enregistrement 6
	Descripteur d'enregistrement 7
	Descripteur d'enregistrement 8
…	…

Les descripteurs de segments sont consultés en premier lorsqu'une recherche est effectuée. Pour chaque descripteur de segment correspondant, les N_r descripteurs d'enregistrement correspondants sont vérifiés pour trouver le ou les enregistrements correspondants. Pour chaque descripteur de segment qui ne correspond pas, les N_r descripteurs d'enregistrement associés peuvent être ignorés. En substance, nous nous retrouvons avec un système qui peut très rapidement écarter les enregistrements qui ne correspondent pas, laissant ceux qui correspondent.

Calcul d'une valeur pour N_r

Il peut être tentant de fixer le nombre d'enregistrements dans un segment à un nombre très élevé. Après tout, si le descripteur du segment ne correspond pas, cela signifie que les N_r enregistrements peuvent être rapidement écartés. Jusqu'à un certain point, c'est correct. Cependant, plus le nombre d'enregistrements par segment est important, plus la probabilité qu'un segment donné contienne une correspondance est élevée. Par exemple, supposons que nous avons 100 enregistrements par segment. Les données de 100 enregistrements sont encodées dans chaque descripteur de segment et les descripteurs d'enregistrements sont regroupés par lots de 100. Supposons maintenant que notre base de données contienne 500 enregistrements et que nous recherchions un terme qui donnera lieu à une seule correspondance. Il est clair dans ce cas qu'un seul descripteur de segment correspondra (en supposant qu'il n'y a pas de fausses correspondances), nous devons donc rechercher dans 100 descripteurs d'enregistrement pour trouver l'enregistrement correspondant. Si le nombre d'enregistrements par segment était de 10, nous obtiendrions toujours une correspondance au niveau du segment, mais il nous suffirait de parcourir 10 descripteurs d'enregistrement pour trouver l'enregistrement correspondant.

Le réglage du nombre d'enregistrements par segment permet d'équilibrer le rejet rapide d'un grand nombre d'enregistrements (en fixant une valeur élevée) et le temps nécessaire à la recherche des descripteurs d'enregistrements dans un segment si celui-ci correspond (en fixant une valeur faible). Il faut également tenir compte des requêtes à termes multiples. Puisqu'un descripteur de segment encode les termes d'un certain nombre d'enregistrements, une requête multi-termes qui contient tous les termes de la requête répartis sur les enregistrements du segment correspondra au niveau du segment, ce qui oblige à vérifier les descripteurs d'enregistrement. Par exemple, si les termes recherchés sont red et house et que le premier enregistrement d'un segment contient le mot red, tandis que le troisième enregistrement contient le mot house, alors le descripteur du segment correspondra (car il code les deux mots). On consulte ensuite les descripteurs d’enregistrements pour voir si certains enregistrements contiennent les deux termes. Comme il n'existe pas d'enregistrement correspondant dans le segment, du temps a été « perdu » à chercher une correspondance inexistante.

Pour déterminer la meilleure valeur pour le nombre d'enregistrements dans un segment, il est important de comprendre comment la base de données sera interrogée. En particulier, si l'on s'attend à un grand nombre de recherches sur un seul terme, il est logique d'avoir un nombre raisonnablement élevé d'enregistrements par segment (disons environ 20-50). Si des recherches multi-termes sont utilisées et que les termes recherchés sont soit liés, soit distincts (c'est-à-dire qu'ils ne se retrouvent pas dans de nombreux enregistrements), la valeur peut également être élevée. Par exemple, le module Taxonomie se compose principalement de termes associés (la Hiérarchie de classification). En cas de recherche d’une combinaison genre-espèce, il est très probable que les deux termes apparaîtront dans le même enregistrement (puisqu'une espèce est un terme plus restreint d'un genre).

Si, toutefois, les requêtes multi-termes contiennent des termes communs non apparentés, une valeur plus petite pour les enregistrements par segment est nécessaire. Par exemple, le module Personnes / Organisations contient des enregistrements qui ont de nombreux termes communs. Imaginez une recherche de tous les artistes de Londres (c'est-à-dire Rôle=artist et Ville=London). Il y a probablement beaucoup d'enregistrements pour lesquels le champ Rôle contient artist, de même que de nombreux enregistrements peuvent avoir une valeur Ville de London. Cependant, il se peut qu'il n'y ait pas beaucoup d'enregistrements qui contiennent les deux termes. Si le nombre d'enregistrements par segment est élevé, un grand nombre de correspondances de segments se produira (parce qu'au moins un enregistrement du segment a un Rôle de artist et qu'au moins un autre enregistrement du segment a une valeur Ville de London). Dans ce cas, il est préférable de fixer le nombre d'enregistrements par segment à un niveau faible, disons environ 10. La configuration de Texpress utilisera une valeur proche de 10 pour le nombre d'enregistrements par segment, car cela permet d'obtenir un index général sans connaissance des données et des requêtes attendues.

Il existe une autre variable utilisée pour déterminer le nombre d'enregistrements dans un segment, la taille de bloc système :

taille du bloc

La taille de bloc est le nombre d'octets qui sont lus ou écrits en une seule fois lors de l'accès à un système de fichiers. Tous les accès au disque du système de fichiers se font en utilisant ce nombre fixe d'octets. Même si vous lisez un octet, le système de fichiers sous-jacent lira toujours des octets de taille de bloc et vous renverra l'octet unique. La taille de bloc d'un système de fichiers est définie lors de la création du système de fichiers. Les tailles de bloc les plus courantes sont 1 024, 4 096 ou 8 192 octets. Texpress assume une taille de bloc par défaut de 4 096 octets.

Afin de permettre une recherche efficace, il est important de s'assurer que toute l'activité du disque se déroule en multiples de la taille de bloc du système de fichiers. Ainsi, lorsque nous sélectionnons le nombre d'enregistrements dans un segment, nous devons nous assurer que la valeur sélectionnée remplit un nombre entier de blocs. Si nous reprenons notre exemple, nous avons vu que la valeur de b (longueur de la chaîne de bits) était de 90 bits ou 12 octets (en arrondissant au chiffre supérieur). Si la taille du bloc est de 4 096 octets, un bloc de disque peut contenir 341 descripteurs d'enregistrement (4 096/12 arrondis au chiffre inférieur). Ainsi, pour notre échantillon de données, la valeur de N_r serait de 341. Comme notre exemple ne comporte que cinq termes, cela conduit à une valeur très élevée. Dans la pratique, les enregistrements contiennent beaucoup plus de termes. Le nombre d'enregistrements par segment est donc généralement d'environ 10 par défaut.

Découpage en bits

La dernière pièce du puzzle de l'indexation est l'utilisation du découpage en bits pour fournir un mécanisme de recherche rapide dans le fichier des descripteurs de segments. Comme nous l'avons vu, un descripteur de segment encode les informations d’enregistrements N_r dans un descripteur. Les descripteurs sont stockés les uns après les autres dans le fichier seg dans le répertoire de la base de données. Lorsqu'une requête est effectuée, la première étape consiste à rechercher chaque descripteur de segment en l'associant par ET au descripteur de segment de la requête pour voir s'il correspond. Lorsque nous obtenons une correspondance, nous vérifions ensuite les descripteurs d'enregistrement de la même manière. Le problème de cette approche est que le fichier seg peut être très volumineux et qu'une recherche séquentielle dans ce fichier peut prendre un certain temps. Le schéma ci-dessous montre une série de descripteurs de segments et un descripteur de requête utilisé pour la recherche :

1	0	1	1	0	1	1	0	1	0	…	(Descripteur de segment 1)
0	1	0	1	0	0	1	1	0	0	…	(Descripteur de segment 2)
1	1	1	0	0	0	0	1	0	1	…	(Descripteur de segment 3)
0	0	0	1	1	0	0	1	1	0	…	(Descripteur de segment 4)
…											(Descripteur de segment N)
0	0	1	0	0	0	1	0	0	0	…	(Descripteur de segment d'interrogation arbitraire)

Il est évident, d'après la table ci-dessus, que pour qu'un descripteur de segment corresponde au descripteur de segment de la requête, il faut un bit 1 dans chaque position où le descripteur de requête a un bit 1. Les autres bits du descripteur ne sont pas pertinents. À l'aide de cette information, le moyen le plus rapide de déterminer quels descripteurs de segment correspondent est de lire des tranches des descripteurs de segment. Lorsque le descripteur de segment de la requête a un bit 1, nous lisons une tranche (c'est-à-dire un bit de chaque descripteur de segment). La tranche est représentée par la zone jaune délimitée par les lignes dans le diagramme. Si nous lisons une tranche pour chaque bit 1 du descripteur de requête et que nous les ajoutons ensemble avec ET, tout bit 1 résultant doit contenir la position d'un descripteur de segment dont tous les bits 1 sont également définis. Dans l'exemple ci-dessus, seul le descripteur de segment 1 correspond au descripteur de segment de la requête.

Le problème de cette approche est que la lecture de bits individuels à partir d'un système de fichiers est extrêmement inefficace. Vous remarquerez cependant que si nous « retournons » le fichier des descripteurs de segments sur le côté, chaque tranche peut maintenant être lue avec un seul accès au disque. La table ci-dessous montre les descripteurs de segment « retournés » :

1	0	1	0	…
0	1	1	0	…
1	0	1	0	…
1	1	0	1	…
0	0	0	1	…
1	0	0	0	…
1	1	0	0	…
0	1	1	1	…
1	0	0	1	…
0	0	1	0	…

Si nous prenons les tranches que nous devons vérifier et que nous les associons avec ET, lorsqu'un bit 1 est activé dans la tranche résultante, le numéro du segment correspond au descripteur de segment de la requête :

1	0	1	0	…	ET
1	1	0	0	…
1	0	0	0	…

D'après notre configuration d'origine, nous savons que nous définissons k bits par terme, donc si une requête d'un seul terme est effectuée, nous devons lire k tranches de bits pour déterminer quels segments correspondent à la requête. Le découpage en bits du fichier de segments est la raison pour laquelle Texpress a une vitesse d'interrogation exceptionnelle.

Un des problèmes du découpage en bits du fichier des descripteurs de segments est que pour stocker les tranches de bits de manière séquentielle, nous devons connaître la longueur d'une tranche de bits. Nous connaissons la longueur du descripteur de segment, elle est de b, donc b tranches de bits sont stockées dans le fichier ; mais quelle est la longueur de chaque tranche ? Afin de déterminer la longueur d'une tranche de bits, nous devons connaître la capacité de la base de données, c'est-à-dire le nombre d'enregistrements qui seront stockés. En utilisant le nombre d'enregistrements par segment (N_r), nous pouvons calculer le nombre de segments nécessaires ; nous utilisons le symbole N_s pour représenter ce nombre. Donc :

Ns = capacité/Nr

Ainsi, la longueur d'une tranche de bits en bits est N_s.

Probabilité de fausse correspondance

Lorsque la probabilité de fausse correspondance a été introduite, elle a été définie comme le nombre de descripteurs à examiner pour obtenir une fausse correspondance. Une valeur de 1 024 est donc interprétée comme la probabilité d'une fausse correspondance tous les 1 024 descripteurs examinés. L'utilisation de cette mesure n'est pas très utile lors de la configuration d'une base de données Texpress, car la probabilité est liée à la capacité de la table plutôt qu'aux descripteurs examinés lors de la requête. Afin de résoudre ce problème, les probabilités de fausses correspondances utilisées par Texpress sont modifiées pour refléter la probabilité d'une fausse correspondance lors d'une recherche dans le fichier de segments et la probabilité d'une fausse correspondance dans un segment lors d'une recherche dans le fichier de descripteurs d'enregistrements. Pour effectuer ces ajustements, les formules suivantes sont utilisées :

Probabilité d'une fausse correspondance au niveau du segment = 1/(fs * Ns)

Probabilité d'une fausse correspondance de segment = 1/(fr * Nr)

Si nous examinons la première formule, nous constatons que la probabilité d'une fausse correspondance au niveau du segment est passée d'un descripteur sur f_s à un sur f_s recherches. Cette modification supprime le nombre de descripteurs de segments de l'équation. Ce faisant, f_s est maintenant une valeur constante quel que soit le nombre de descripteurs de segments. Une modification similaire a été apportée à la probabilité de fausse correspondance pour les descripteurs d'enregistrements. Le nombre d'enregistrements par segment a été introduit afin que la probabilité soit désormais le nombre de segments examinés avant une fausse correspondance, plutôt que le nombre d'enregistrements.

Nous avons passé beaucoup de temps à examiner les principes fondamentaux du mécanisme d'indexation de Texpress. Il y a cependant une variable qui nécessite une étude plus approfondie, car elle joue un rôle important dans la génération automatique des valeurs de configuration. La variable est le nombre d'atomes indexés par enregistrement (i_s et i_r).

Un atome est un composant de base indexable. Chaque atome correspond à un composant recherchable dans les index Texpress. La définition d’un atome dépend du type de champ de données. La table ci-dessous indique, pour chaque type de données pris en charge, ce qui constitue un atome :

float integer	Une valeur numérique simple constitue un atome.
date	Chaque valeur de date est constituée de trois composants (année, mois, jour). Chaque composant rempli est un atome. Par exemple, si un champ de date contient 2008/1/1, le nombre d'atomes est de trois, alors qu'une valeur de date de 2008/1/ ne comporte que deux atomes.
heure	Comme pour les dates, les valeurs temporelles sont constituées de trois composants (heure, minute, seconde). Chaque composant qui a une valeur est un atome. Par exemple, une valeur temporelle de 10:23:15.0 contient trois atomes, tandis que 10:20 en contient deux.
latitude longitude	Les valeurs de latitude et de longitude sont constituées de quatre composants (degré, minute, seconde, direction). Chaque composant ayant une valeur est un atome. Par exemple, une latitude de 28:12:12.123:N est constituée de quatre atomes, tandis que 28:::N est constituée de deux atomes.
chaîne	Une valeur de chaîne (rarement utilisée dans EMu) est une valeur de texte indexée comme un atome. La valeur des données est débarrassée de toute ponctuation et la chaîne de caractères qui en résulte forme un seul composant. Par exemple, une valeur de chaîne « 12.temp.1 » produirait un atome de « 12 temp 1 », qui est indexé comme une valeur unique. Pour récupérer les valeurs d'une chaîne, vous devez saisir la chaîne complète, plutôt qu'un simple mot.
text	Pour les données textuelles, chaque mot unique du texte constitue un atome. Un mot est une séquence de caractères alphabétiques ou numériques délimitée par la ponctuation (la casse des caractères est ignorée). Par exemple, une valeur textuelle « This is a text value - it contains a series of words » contient dix atomes (il y a onze mots, mais « a » est répété, donc le nombre de mots uniques est de dix).

Si une colonne peut contenir une liste de valeurs, le nombre d'atomes est la somme des atomes de chaque valeur individuelle, les atomes en double étant supprimés. Ainsi, si vous avez une colonne de nombres entiers qui accepte des valeurs multiples et que les données sont 10, 12, 14 et 12, le nombre d'atomes est de trois (car 12 est en double).

La table ci-dessus reflète ce qu'est un atome pour les types de données standard utilisés par Texpress. Texpress propose toutefois des schémas d'indexation supplémentaires qui offrent des caractéristiques de recherche différentes. La table ci-dessous détaille ce qui constitue un atome pour chacun de ces systèmes d'indexation supplémentaires :

Indexation Null	L'indexation null permet une recherche rapide lorsqu'il s'agit de déterminer si une colonne contient une valeur ou si elle est vide (c'est-à-dire pour les recherches avec les caractères génériques *, !*, + et !+). Il est disponible pour tous les types de données. Il y a un atome par colonne pour toutes les colonnes dont l'indexation null est activée, qu'elles contiennent plusieurs valeurs, une seule valeur ou qu'elles soient vides.
Indexation partielle	L'indexation partielle permet une recherche rapide lorsque le terme de la recherche spécifie des lettres de début suivies de caractères génériques (par exemple, a*, fre?, bil[ck]*). Elle est disponible pour les types de données texte et chaîne. Un atome pour l'indexation partielle est le nombre de composants partiels uniques (mots pour les données textuelles, valeur entière pour les données de chaîne) pour chacun des termes partiels. Par exemple, considérons la valeur textuelle « I like lollies. ». Elle se compose de trois mots : I like lollies Si nous fournissons une indexation partielle pour un et trois caractères, les atomes d'un caractère sont : i l et les trois atomes de caractères sont : lik lol Le nombre d'atomes pour l'indexation partielle dans l'exemple ci-dessus est donc de quatre. Pour les colonnes qui contiennent plusieurs valeurs de texte, le nombre d'atomes est la somme des atomes par valeur de texte, les atomes en double étant supprimés.
Indexation lemmatique (Stem indexing)	L'indexation lemmatique permet de rechercher tous les mots qui ont la même racine. Cela permet aux utilisateurs de trouver un mot indépendamment de sa forme (par exemple, si vous recherchez electric, vous trouverez electric, electricity, electrical, electrics, etc.) Elle est disponible pour les types de données texte. L'indexation lemmatique utilise le même mécanisme que l'indexation standard, sauf que le mot est transformé en son mot racine avant d'être indexé. Le nombre d'atomes générés est donc similaire à celui d'une indexation normale basée sur le texte (sauf que le nombre d'atomes uniques est plus faible, car de nombreux mots ont la même racine). Ainsi, hypothétiquement, le nombre d'atomes pour l'indexation lemmatique est à peu près le même que celui de l'indexation textuelle. Afin de réduire la charge d'indexation (sans perdre en vitesse de recherche), EMu indexe complètement chaque atome lemmatique (c'est-à-dire qu'il définit k bits), mais réduit l'indexation pour le mot du texte à 2 bits supplémentaires par mot.
Indexation phonétique (Phonetic indexing)	L'indexation phonétique permet de rechercher des mots sonnant pareil, c'est-à-dire qui contiennent les mêmes groupes de sons (par exemple, Steph et Steff sont phonétiquement identiques). L'indexation phonétique fonctionne exactement de la même manière que l'indexation lemmatique, sauf que les groupes de sons d'un mot constituent l'atome plutôt que la racine du mot. Comme pour l'indexation lemmatique, deux bits supplémentaires sont définis pour le mot texte afin de permettre une recherche basée sur le texte.
Indexation des phrases	L'indexation des phrases permet une recherche rapide pour les recherches basées sur des phrases, c'est-à-dire les recherches où les termes de la requête sont placés entre guillemets (par exemple, « red house »). Elle est disponible pour le type de données texte. Un atome pour la requête basée sur les phrases est le nombre de combinaisons de mots doubles adjacents dans les données textuelles qui ne sont pas séparés par un caractère de fin de phrase. Par exemple, considérons le texte « I like Lollies. Do you? » Les combinaisons de mots doubles adjacents sont : I - like like - lollies do - you Chacune de ces combinaisons est un atome, mais EMu ne définit qu'un seul bit pour fournir une requête basée sur une phrase, plutôt que les k bits normaux.

Maintenant que nous savons ce qu'est un atome, nous devons examiner comment Texpress calcule le nombre d'atomes dans un enregistrement.

Lors de l'explication des variables de configuration utilisées pour configurer une table Texpress, le nombre d'atomes par enregistrement (i) n’a pas été révélé. L'exemple de travail a utilisé une valeur de cinq sur la base des données trouvées dans un seul enregistrement. En fait, la détermination d'une valeur pour le nombre de termes d'indexation par enregistrement peut être assez complexe. Il s'avère également que la valeur choisie a un impact important sur la configuration globale du système (ce qui est prévisible puisqu'elle joue un rôle important dans le calcul de b (longueur du descripteur en bits)). Texpress 8.2.01 a introduit des changements dans le système d'indexation permettant de suivre dynamiquement le nombre d'atomes par enregistrement. Grâce à ces modifications, Texpress peut fournir de très bonnes configurations quelle que soit la distribution du nombre d'atomes par enregistrement.

Comment Texpress décide-t-il du nombre d'atomes par enregistrement ? Tout d'abord, nous devons examiner quel est le nombre d'atomes dans un enregistrement pour un enregistrement donné. D'après la section précédente (Qu'est-ce qu'un atome ?), le nombre d'atomes dans un enregistrement donné est composé de trois chiffres :

conditions	Le nombre de termes pour lesquels k bits sont définis lors de la construction du descripteur. La plupart des atomes entrent dans cette catégorie.
extra	Le nombre d'atomes supplémentaires où deux bits sont définis pour le mot complet. Les atomes supplémentaires résultent de la recherche lemmatique et de la recherche phonétique.
adjacent	Le nombre d'atomes adjacents où une combinaison de deux mots est indexée ensemble, ce qui fait qu'un bit est défini.

Prenons un exemple. Si nous avons un enregistrement avec un champ de texte dont l'indexation lemmatique est activée et qu'il contient le texte suivant I like lollies do you?alors la décomposition des atomes est :

Type d'index	Nombre	Bits définis	Atomes
conditions	5	k	i, like, lollies, do, you
extras	5	2	i, lik, lol, do, you
adjacent	4	1	i-like, like-lollies, lollies-do, do-you

Afin d'obtenir le nombre d'atomes pour l'enregistrement, nous devons calculer un nombre pondéré d'atomes basé sur le nombre de bits définis. La formule est la suivante :

i = (termes * k + extra * 2 + adjacent * 1)/k

Ainsi, en reprenant notre exemple et en supposant que k=5, le nombre d'atomes pour l'enregistrement test est (5 * 5 + 5 * 2 + 4 * 1) / 5 ou 8 (arrondi au chiffre supérieur). Étant donné que nous avons deux valeurs pour le nombre de bits à définir par terme indexé (k_s et k_r pour les descripteurs de segment et les descripteurs d'enregistrement respectivement), nous obtenons deux valeurs pondérées pour le nombre d'atomes : une pour le niveau segment (i_s) et une pour le niveau enregistrement (i_r).

Comme vous pouvez l'imaginer, cela peut prendre beaucoup de temps de calculer le nombre d'atomes dans un enregistrement pour chaque enregistrement d'une table. Texpress vous facilite la tâche en stockant les trois chiffres nécessaires pour déterminer i avec chaque descripteur d'enregistrement. Lorsqu'un enregistrement est inséré ou mis à jour, les comptes sont ajustés pour refléter les données stockées dans l'enregistrement. En utilisant texanalyse les atomes pour chaque enregistrement peuvent être visualisés. L'option -r est utilisée pour vider les comptes bruts :

texanalyse -r eparties

Conditions,Extra,Adjacent,RecWeighted,SegWeighted

118,9,14,123,122

126,10,21,132,131

102,3,2,103,103

139,12,39,148,146

130,12,28,137,136

138,15,36,147,145

136,15,36,145,143

…

Les trois premières colonnes de chiffres correspondent au nombre de termes, d'atomes supplémentaires et d'atomes adjacents. Les deux derniers nombres sont le nombre pondéré d'atomes pour le niveau du descripteur d'enregistrement (i_r) et le niveau du descripteur de segment (i_s) respectivement. Ces chiffres constituent l'entrée brute utilisée par Texpress pour déterminer le nombre global d'atomes à utiliser pour la configuration.

Une méthode pour obtenir le nombre d'atomes à utiliser pour la configuration consiste à prendre la moyenne du nombre pondéré d'atomes dans chaque enregistrement. Dans ce cas, un certain pourcentage d'enregistrements serait inférieur à la valeur moyenne et le reste supérieur. Pour les enregistrements avec la valeur moyenne, la densité de bits des descripteurs générés sera d (25 % par défaut). Pour les enregistrements dont le nombre d'atomes est inférieur à la moyenne, la densité de bits sera inférieure à d, et pour ceux qui sont supérieurs à la moyenne, elle sera supérieure à d. D'après nos premiers calculs :

k = log(f) / log(100 / d)

Nous devons maintenir la densité de bits (d) à environ 25 %, étant donné que k est fixe, sinon la probabilité de fausse correspondance diminue et les fausses correspondances sont plus probables. Nous devons veiller à ce que la grande majorité des enregistrements aient une densité de bits de 25 % ou moins. Pour ce faire, nous ne pouvons pas utiliser le nombre moyen d'atomes par enregistrement, nous devons plutôt choisir une valeur plus élevée.

Si nous calculons le nombre moyen d'atomes par enregistrement et que nous connaissons l'écart-type, nous pouvons utiliser l'analyse statistique pour déterminer une valeur pour le nombre d'atomes qui garantit que la plupart des enregistrements soient inférieurs à cette valeur (et donc que la densité de bits est inférieure à 25 %). Si le nombre d'atomes dans chaque enregistrement suit une distribution normale, ce qui est généralement le cas lorsque les données proviennent d'une seule source, l'analyse montre que 95,4 % des enregistrements auront une valeur du nombre d'atomes inférieure à la moyenne plus deux fois l'écart-type, et que 99,7 % des enregistrements auront une valeur du nombre d'atomes inférieure à la moyenne plus trois fois l'écart-type. Le calcul de l'écart-type du nombre d'atomes dans chaque enregistrement pourrait prendre un certain temps. Heureusement, texanalyse peut être utilisé pour déterminer cette valeur. Si texanalyse est exécuté sans options, le résultat suivant est affiché :

texanalyse eparties

Analyse des atomes indexés par enregistrement

====================================

+---------+---------+---------+

|  Atomes  |Records|Records|Records|

|         |  (Rec)  |  (Seg)  |

+---------+---------+---------+

|     93  |      0  |      1  |

|     94  |      1  |      0  |

|     95  |      0  |      3  |

|     96  |      3  |      2  |

|     97  |      2  |      0  |

|     98  |      3  |      3  |

|     99  |      8  |      8  |

|    100  |      0  |      2  |

|    101  |      3  |      1  |

|    102  |      1  |      1  |

|    103  |     13  |     15  |

|    104  |   2198  |   2223  |

|    105  |    966  |    976  |

|    106  |     43  |    290  |

|    107  |    288  |     94  |

…

|    397  |      0  |      0  |

|    398  |      1  |      0  |

+---------+---------+---------+

Analyse au niveau de l’enregistrement

=====================

Nombre total d’enregistrements                     :    50046

Nombre total de termes indexés               :  6169873

Nombre moyen de termes indexés             :    123,3

Écart-type                          :     18,5

Enregistrements <= moyenne                          :    32726 (65,4<= 123,3)

Enregistrements <= moyenne + 1 * écart-type :    46156 (92,2<= 141,8)

Enregistrements <= moyenne + 2 * écart-type :    48310 (96,5<= 160,4)

Enregistrements <= moyenne + 3 * écart-type :    49114 (98,1<= 178,9)

Enregistrements <= moyenne + 4 * écart-type :    49456 (98,8<= 197,4)

Enregistrements <= moyenne + 5 * écart-type :    49638 (99,2<= 215,9)

Enregistrements <= moyenne + 6 * écart-type :    49732 (99,4<= 234,5)

Enregistrements <= moyenne + 7 * écart-type :    49838 (99,6<= 253,0)

Enregistrements <= moyenne + 8 * écart-type :    49938 (99,8<= 271,5)

Enregistrements <= moyenne + 9 * écart-type :    49990 (99,9<= 290,1)

Enregistrements <= moyenne + 10 * écart-type :    50014 (99,9<= 308,6)

Enregistrements <= moyenne + 11 * écart-type :    50027 (100,0<= 327,1)

Enregistrements <= moyenne + 12 * écart-type :    50036 (100,0<= 345,7)

Enregistrements <= moyenne + 13 * écart-type :    50038 (100,0<= 364,2)

Enregistrements <= moyenne + 14 * écart-type :    50044 (100,0<= 382,7)

Enregistrements <= moyenne + 15 * écart-type :    50046 (100,0<= 401,3)

Analyse au niveau des segments

======================

Nombre total d’enregistrements                     :    50046

Nombre total de termes indexés               :  6112301

Nombre moyen de termes indexés             :    122,1

Écart-type                          :     17,8

Enregistrements <= moyenne                          :    32744 (65,4<= 122,1)

Enregistrements <= moyenne + 1 * écart-type :    46163 (92,2<= 139,9)

Enregistrements <= moyenne + 2 * écart-type :    48306 (96,5<= 157,7)

Enregistrements <= moyenne + 3 * écart-type :    49126 (98,2<= 175,5)

Enregistrements <= moyenne + 4 * écart-type :    49459 (98,8<= 193,2)

Enregistrements <= moyenne + 5 * écart-type :    49645 (99,2<= 211,0)

Enregistrements <= moyenne + 6 * écart-type :    49728 (99,4<= 228,8)

Enregistrements <= moyenne + 7 * écart-type :    49832 (99,6<= 246,6)

Enregistrements <= moyenne + 8 * écart-type :    49938 (99,8<= 264,4)

Enregistrements <= moyenne + 9 * écart-type :    49989 (99,9<= 282,1)

Enregistrements <= moyenne + 10 * écart-type :    50014 (99,9<= 299,9)

Enregistrements <= moyenne + 11 * écart-type :    50027 (100,0<= 317,7)

Enregistrements <= moyenne + 12 * écart-type :    50036 (100,0<= 335,5)

Enregistrements <= moyenne + 13 * écart-type :    50038 (100,0<= 353,2)

Enregistrements <= moyenne + 14 * écart-type :    50044 (100,0<= 371,0)

Enregistrements <= moyenne + 15 * écart-type :    50046 (100,0<= 388,8)

La table sous le titre Analyse des atomes indexés par enregistrement montre pour un nombre donné d'atomes (dans la colonne Atomes) combien d'enregistrements ont ce nombre d'atomes au niveau de l'enregistrement (Enregistrements (Enr)) et au niveau du segment (Enregistrements (Seg)). L’Analyse au niveau de l'enregistrement et l'Analyse au niveau du segment indiquent le nombre moyen d'atomes et l'écart-type pour chaque niveau. La table en dessous de l'écart-type indique le nombre d'enregistrements inférieurs à la moyenne plus un multiple de l'écart-type. Le premier nombre entre parenthèses est le pourcentage d'enregistrements inférieurs à la valeur et le nombre après le signe égal est le nombre d'atomes. Par exemple, si vous prenez la ligne :

Records <= average + 3 * standard deviation:    49126 (98.2<= 175.5)

cela indique que 49 126 enregistrements sont inférieurs à la moyenne plus trois fois l'écart-type, ce qui représente 98,2 % des enregistrements. Le nombre d'atomes représenté par la moyenne plus trois fois l'écart-type est de 175,5. En utilisant cette table, il est possible de déterminer quelles seraient les bonnes valeurs pour i_s et i_r. Souvenez-vous, nous voulons que la plupart des enregistrements soient inférieurs à la valeur sélectionnée, dans la plupart des cas au-dessus de 98 %. En utilisant ceci comme guide, pour la sortie ci-dessus, une valeur appropriée pour i_r serait 180 (178,9 arrondi au nombre supérieur) et pour i_s 175 (175,5 arrondi au nombre inférieur). Même si ces valeurs semblent bonnes à première vue, il convient de considérer également les extrêmes supérieurs. Pour l'analyse au niveau des enregistrements, le nombre maximum d'atomes dans un enregistrement est de 398. Si nous utilisons une valeur de 180 pour le nombre d'atomes au niveau de l'enregistrement, cela signifie que l'enregistrement avec le nombre maximum d'atomes fixe 2,2 fois le nombre de bits qu'un enregistrement avec 180 atomes. Si nous appliquons cela à la densité de bits, cela correspond à 55 % (25 % * 2,2). Si nous utilisons la valeur 5 pour k (cinq bits par atome), la probabilité de fausse correspondance pour l'enregistrement comportant 398 atomes est la suivante :

(55/100)5 ≈ 0.05 or 1/20 

Ainsi, l'enregistrement avec 398 atomes a une probabilité de fausse correspondance de 1/20 au lieu du 1/1024 requis. En général, il s'agit d'une valeur acceptable, à condition qu'il n'y ait pas beaucoup d'enregistrements avec une probabilité aussi élevée. Toutefois, si la densité de bits est supérieure à 75 % pour l'enregistrement comportant le nombre maximal d'atomes, il peut être intéressant d'augmenter la valeur de i de manière à diminuer la densité (en faisant en sorte que i représente environ un tiers de la valeur du nombre maximal d'atomes). En général, cela n'est nécessaire que dans des cas extrêmes et ne se produit que lorsqu'un grand nombre de sources de données sont chargées dans une table.

L'idée d'ajouter un certain nombre d'écarts types au nombre moyen d'atomes nous fournit notre dernière variable :

v

Le nombre d'écarts types à ajouter au nombre moyen d'atomes par enregistrement pour déterminer la valeur de i, communément appelé la variance. Puisque nous avons un segment et une valeur de niveau d'enregistrement pour i, nous avons également un segment et une valeur de niveau d'enregistrement pour v. La valeur par défaut pour le niveau du segment est 2,0, et pour le niveau de l'enregistrement 3,0. C'est-à-dire que nous ajoutons deux fois l'écart-type pour calculer la valeur de is et trois fois l'écart-type pour calculer ir.

Il peut être opportun à ce stade de résumer les variables utilisées dans le cadre de la configuration d'une base de données Texpress. Comme Texpress utilise un schéma à deux niveaux, il y a deux ensembles de variables, un pour le niveau du segment et un pour le niveau de l'enregistrement. Les variables portant l'indice r s'appliquent aux descripteurs d'enregistrements, tandis que celles portant l'indice s sont utilisées pour les descripteurs de segments :

Variable	Description	Valeur par défaut
Ns	Nombre de descripteurs de segments	Calculé à partir de la capacité
Nr	Nombre de descripteurs d'enregistrement par segment	Calculé avec un minimum de 10
kr	Bits à définir par terme dans le descripteur d'enregistrement	Calculé
ks	Bits à définir par terme dans le descripteur de segment	Calculé
br	Longueur en bits d'un descripteur d'enregistrement	Calculé
bs	Longueur en bits d'un descripteur de segment	Calculé
fr	Probabilité de fausse correspondance pour les descripteurs d'enregistrements	1024
fs	Probabilité de fausse correspondance pour les descripteurs de segments	4
dr	Densité de bits des descripteurs d'enregistrement	25 %
ds	Densité de bits des descripteurs de segments	25 %
ir	Termes indexés par descripteur d'enregistrement	Calculé à partir des données
is	Termes indexés par descripteur de segment	Calculé à partir des données
vr	Nombre d'écarts-types à ajouter à la moyenne au niveau de l'enregistrement	3.0
vs	Nombre d'écarts-types à ajouter à la moyenne au niveau du segment	2.0
taille du bloc	Taille du système de fichiers en lecture/écriture en octets	4096

L'outil texanalyse permet d'obtenir des informations sur le nombre d'atomes par enregistrement. Il prend en charge à la fois le niveau de l'enregistrement et le niveau du segment. L'utilisation principale de texanalyse est de vérifier que la valeur utilisée pour le nombre d'atomes par enregistrement (i) est appropriée : en particulier, il s'agit de vérifier que les enregistrements avec le nombre maximum d'atomes par enregistrement sont dans une plage acceptable de i. Nous définissons l'acceptable comme étant compris dans le triple de la valeur de i lorsqu'une densité de bits (d) de 25 % est utilisée. Il est également instructif d'utiliser texanalyse pour produire les données brutes qui peuvent être transmises à des tableurs pour analyse. Le message d'utilisation est :

Utilisation : texanalyse [-R] [-V] [-c|-r] [-s] dbname

Les options sont :

-c      imprimer l’analyse au format CSV

-r      imprimer les données brutes au format CSV

-s      supprimer les lignes vides

Si les données atomiques brutes par enregistrement sont requises, l'option -r est utilisée :

texanalyse -r eparties

Conditions,Extra,Adjacent,RecWeighted,SegWeighted

118,9,14,123,122

126,10,21,132,131

102,3,2,103,103

139,12,39,148,146

…

La sortie est au format CSV (valeurs séparées par des virgules) pour être chargée dans un tableur ou une base de données. Les données contiennent le nombre d'atomes du terme, celui d'atomes supplémentaires et d'atomes adjacents pour chaque enregistrement de la table. Le nombre pondéré d'atomes au niveau de l'enregistrement et du segment est également indiqué.

Il est également possible d'exporter au format CSV le nombre d'enregistrements, tant au niveau des enregistrements que des segments, qui ont un nombre donné d'atomes :

texanalyse -c eparties

Atomes,RecRecords,SegRecords

101,3,1

102,1,1

103,13,15

104,2198,2223

105,966,976

106,43,290

107,288,94

108,93,19

109,536,527

110,15,13

111,6,20

…   

Les résultats peuvent être chargés dans des tableurs pour être analysés. Le graphique ci-dessous montre le nombre d'enregistrements pour chaque nombre d'atomes de la sortie ci-dessus au niveau des enregistrements :

La production d'un graphique du nombre d'enregistrements avec chaque nombre d'atomes fournit un mécanisme utile pour déterminer dans quelle mesure la distribution du nombre d'atomes dans un enregistrement est proche d'une distribution normale. En particulier, il peut être utilisé pour voir si le chargement de sources de données distinctes a donné lieu à la superposition d'un certain nombre de distributions normales (une par source de données). Le graphique au début de cet article montre clairement qu'au moins trois sources de données distinctes ont été chargées dans la table Personnes / Organisations.

L'utilisation finale de texanalyse est de produire un résumé détaillant le nombre moyen d'atomes par enregistrement et l'écart-type. Une liste de la moyenne plus un nombre entier d'écarts-types est également indiquée :

elocations texanalyse

Analyse des atomes indexés par enregistrement

====================================

+---------+---------+---------+

|  Atomes  |Records|Records|Records|

|         |  (Rec)  |  (Seg)  |

+---------+---------+---------+

|     49  |     17  |     17  |

|     50  |      0  |      0  |

…

|    106  |      0  |      1  |

+---------+---------+---------+

Analyse au niveau de l’enregistrement

=====================

Nombre total d’enregistrements                     :     1419

Nombre total de termes indexés               :    90309

Nombre moyen de termes indexés             :     63,6

Ecart-type                          :      9,4

Enregistrements <= moyenne                          :     1170 (82,5<= 63,6)

Enregistrements <= moyenne + 1 * écart-type :     1244 (87,7<= 73,1)

Enregistrements <= moyenne + 2 * écart-type :     1313 (92,5<= 82,5)

Enregistrements <= moyenne + 3 * écart-type :     1323 (93,2<= 91,9)

Enregistrements <= moyenne + 4 * écart-type :     1418 (99,9<= 101,4)

Enregistrements <= moyenne + 5 * écart-type :     1419 (100,0<= 110,8)

Analyse au niveau des segments

======================

Nombre total d’enregistrements                     :     1419

Nombre total de termes indexés               :    91805

Nombre moyen de termes indexés             :     64,7

Écart-type                          :      9,8

Enregistrements <= moyenne                          :     1167 (82,2<= 64,7)

Enregistrements <= moyenne + 1 * écart-type :     1243 (87,6<= 74,5)

Enregistrements <= moyenne + 2 * écart-type :     1311 (92,4<= 84,3)

Enregistrements <= moyenne + 3 * écart-type :     1323 (93,2<= 94,1)

Enregistrements <= moyenne + 4 * écart-type :     1417 (99,9<= 103,9)

Enregistrements <= moyenne + 5 * écart-type :     1419 (100,0<= 113,7)

Les tables d'analyse à la fin peuvent être utilisées pour déterminer si le nombre calculé d'atomes par enregistrement est approprié. La valeur calculée du niveau d'enregistrement est la moyenne plus trois fois l'écart-type et la valeur du segment est la moyenne plus deux fois l'écart-type. La vérification standard consiste à s'assurer que le nombre maximal d'atomes est inférieur à trois fois la valeur choisie pour i (en supposant une densité de bits (d) de 25 %).

Afin de tester l'efficacité d'une configuration, il est utile de pouvoir déterminer la densité de bits pour tous les descripteurs de segments et d'enregistrements. L'utilitaire texdensity fournit cette fonctionnalité. Le message d'utilisation est :

Utilisation : texdensity [-R] [-V] [[-cr|-cs] | [-dr|-ds]] [-s] [-nrn -nsn] dbname

Les options sont :

-cr     imprime la densité du descripteur d'enregistrement au format CVS

-cs     imprime la densité du descripteur de segment au format CVS

-dr     imprime la densité du descripteur d'enregistrement

-dr     imprime la densité du descripteur de segment

-s      supprime les valeurs vides

-nrn    scan n descripteurs d’enregistrements

-nsn    scan n descripteurs de segments

Si une analyse de la densité de bits est nécessaire, les options -cr ou -cs peuvent être utilisées pour sortir au format CSV le nombre de bits définis et la densité de bits par enregistrement ou descripteur de segment respectivement :

texdensity -cr elocations

Index,Bits,Total,Densité

0,424,2384,17.79

1,405,2384,16.99

2,404,2384,16.95

3,438,2384,18.37

…

La colonne Index est l'index du descripteur d'enregistrement (ou du descripteur de segment si -cs est utilisé). Viennent ensuite le nombre de bits définis, puis le nombre total de bits qui pourraient être définis et enfin la densité de bits en pourcentage. En général, la densité de bits doit être inférieure à la valeur par défaut de 25 %.

Il est également possible d'obtenir la densité de bits moyenne, l'écart-type et la densité de bits maximale :

texdensity -ds elocations

Analyse des descripteurs de segments

===========================

Descripteur  Bits définis  Total des bits  Densité

+----------+----------+----------+----------+

|       0  |    1193  |   17280  |    6.90  |

|       1  |    1164  |   17280  |    6.74  |

|       2  |    1007  |   17280  |    5.83  |

|       3  |     971  |   17280  |    5.62  |

…

|     135  |       0  |   17280  |    0.00  |

+----------+----------+----------+----------+

Nombre de descripteurs : 119

Densité moyenne        : 4,42

Écart-type     :1,10

Densité maximale        : 10,39

La sortie ci-dessus montre le résumé pour les descripteurs de segment de la table elocations. Comme la densité maximale de 10,39 est bien inférieure à la densité requise de 25 %, cela indique que la valeur du nombre d'atomes par enregistrement peut être abaissée. Le nombre calculé d'atomes par enregistrement au niveau du segment était de 83. Si nous diminuons proportionnellement le nombre d'atomes par enregistrement (83 * 10.39 / 25), le nombre d'atomes à utiliser est de 34. Après avoir reconfiguré le nombre d'atomes par enregistrement au niveau du segment à 34, on trouve le résumé de densité suivant :

Nombre de descripteurs : 119

Densité moyenne        : 10,45

Écart-type     : 2,44

Densité maximale        : 23,37

Sur la base de ce résultat, le chiffre pourrait être encore abaissé, car la densité de bits moyenne est de 10,45 et si nous ajoutons trois fois l'écart-type, nous obtenons 17,77 (10.45 + 3 * 2.44), ce qui est encore bien inférieur à 25 %. La raison pour laquelle les densités de bits des descripteurs de segments sont généralement plus faibles que celles des descripteurs d'enregistrements est due à la répétition des atomes dans tous les enregistrements qui composent le descripteur de segment. En particulier, il existe un certain nombre de champs dans EMu qui contiennent la même valeur pour tous les enregistrements d'un segment (par exemple, Statut de l'enregistrement, Publié sur l'Internet, Publié sur l'Intranet, Sécurité au niveau de l'enregistrement, etc.) Puisque chaque enregistrement du segment a la même valeur dans ces champs, nous ne devrions compter l'atome qu'une seule fois, mais Texpress n'a pas de mécanisme disponible pour suivre le nombre d'atomes répétés dans un segment, donc on suppose le pire des scénarios où aucun atome n'est répété. En général, cela se traduit par des fichiers de descripteurs de segments plus volumineux qu'ils ne devraient l'être. Outre le fait qu'il utilise plus d'espace disque, le mécanisme de requête n'est pas affecté de manière flagrante puisque des tranches de bits sont lues plutôt que des descripteurs de segment complets. Il est possible d'ajuster le nombre d'atomes par enregistrement au niveau du segment, ce qui permet dans certains cas de réaliser des économies substantielles d'espace disque.

La section suivante, consacrée à la définition des paramètres de configuration, détaille la manière dont ces paramètres sont définis.

L'utilitaire texconf est un programme frontal de l'outil de configuration de Texpress. En utilisant texconf, il est possible de modifier n'importe quelle variable de configuration et de voir l'effet qu'elle a sur la configuration finale (c'est-à-dire les valeurs de N_r, N_s, b_r, b_s, k_r et k_s). Le message d'utilisation est :

Utiliser : texconf [-R] [-V] [-bn] [-cn] [-drn] [-dsn] [-frn] [-fsn] [-mn] [-irn -isn -nrn -nsn -vrn -vsn] dbname

Les options sont :

-bn             taille de bloc du système de fichiers de n octets

-cn             capacité de n enregistrements

-drn            densité de bits du descripteur d'enregistrement de n

-dsn            densité de bits du descripteur de segment de n

-frn            descripteur d'enregistrement probabilité de fausse correspondance de n

-fsn            probabilité de fausse correspondance du descripteur de segment de n

-mn             nombre minimum d'enregistrements par segment de n

-irn            descripteur d'enregistrement termes indexés par enregistrement de n

-est            termes indexés du descripteur de segment par enregistrement de n

-nrn            scanner n enregistrements pour déterminer la valeur de -ir

-nrn            scanner n enregistrements pour déterminer la valeur de -is

-vrn            augmenter la valeur de -ir de n écarts-types

-vsn            augmente la valeur de -is de n écarts-types

Un examen attentif des options montre que la plupart correspondent aux variables abordées dans cet article. En utilisant les options, vous pouvez tester l'effet de la modification des variables. Exécuter texconf sans aucune option générera une configuration basée sur les valeurs par défaut en utilisant la capacité actuelle de la base de données :

elocations de texconf

Configuration de l'index

===================

Capacité de la base de données (dans les enregistrements)            :     1632

Nombre de segments (Ns)                      :      136

Nombre d’enregistrements par segment (Nr)           :       12

Mots par descripteur de segments                 :      540

Mots par descripteur d’enregistrements                  :       79

Bits définis par terme indexé (segment)          :        5

Bits définis par terme indexé (enregistrement)           :        7

Configuration du descripteur d'enregistrement

===============================

Documents scannés pour déterminer les termes indexés   :     1419

Nombre moyen de termes indexés              :     63,6

Écart-type des termes indexés          :      9,4

Écarts types pour augmenter la moyenne      :      3,0

Nombre attendu de termes indexés             :       92

Probabilité de fausse correspondance (enregistrement)                      : 0,000081   [1 / (1024 * Nr)]

Longueur de balise (en bits) de descripteur d’enregistrement          :      144

Bits définis par terme supplémentaire                      :        2

Bits définis par terme adjacent                   :        1

Configuration du descripteur de segment

================================

Segments analysés pour déterminer les termes indexés :      118

Nombre moyen de termes indexés              :    776,0

Écart-type des termes indexés          :    108,8

Écarts types pour augmenter la moyenne      :      2,0

Nombre attendu de termes indexés             :      994

Nombre moyen de termes indexés par enregistrement   :     64,7

Écart-type des termes par enregistrement       :      9,1

Nombre attendu de termes indexés par enregistrement :       82

Probabilité de fausse correspondance                      : 0,001838   [1 / (4 * Ns)]

Bits définis par terme supplémentaire                      :        2

Bits définis par terme adjacent                   :        1

Tailles d'index

===========

Taille de segment                                 :     4096

Taille du fichier descripteur de segment                 :  286,88 K

Taille du fichier descripteur d’enregistrement                  :  544,00 K

Pourcentage de fichier descripteur d’enregistrement perdu     :    1,56 %

Total du surcoût d’index                         :  830,88 K

La sortie est divisée en quatre secteurs. Le premier (Configuration d’index) imprime les valeurs de configuration générées. Ces valeurs peuvent être saisies à l'écran de configuration de Texpress. Le deuxième (Configuration du descripteur d'enregistrement) détaille les paramètres utilisés lors du calcul de la configuration du descripteur d'enregistrement. Le troisième (Configuration du descripteur de segment) indique les valeurs utilisées lors du calcul de la configuration du descripteur de segment. Le dernier (Tailles d’index) indique la taille des fichiers d'index requis pour la configuration générée.

La table ci-dessous indique où se trouve chacune des variables de configuration :

Variable	Nom dans texconf
Ns	Nombre de segments (Ns)
Nr	Nombre d’enregistrements par segment (Nr)
bs	Mots par descripteur de segments (multiplier par 32)
br	Mots par descripteur d'enregistrement (multiplier par 32)
ks	Bits définis par terme indexé (segment)
kr	Bits définis par terme indexé (enregistrement)
is	Nombre attendu de termes indexés [Configuration des descripteurs de segment]
ir	Nombre attendu de termes indexés [Configuration des descripteurs d’enregistrements]
fs	Probabilité de fausse correspondance [Configuration du descripteur de segment]
fr	Probabilité de fausse correspondance [Configuration du descripteur d’enregistrement]
vs	Écarts-types pour augmenter la moyenne [Descripteur de segment Configuration]
vr	Écarts-types pour augmenter la moyenne [Descripteur d'enregistrement Configuration]

Disons qu'après une certaine analyse, nous décidons que le nombre moyen d'atomes par enregistrement au niveau du segment devrait être de 34 au lieu de 82. On peut exécuter :

texconf -is34 elocations

Configuration de l'index

===================

Capacité de la base de données (dans les enregistrements)            :     1632

Nombre de segments (Ns)                      :      136

Nombre d’enregistrements par segment (Nr)           :       12

Mots par descripteur de segments                 :      222

Mots par descripteur d’enregistrements                  :       79

Bits définis par terme indexé (segment)          :        5

Bits définis par terme indexé (enregistrement)           :        7

…

Tailles d'index

===========

Taille de segment                                 :     4096

Taille du fichier du descripteur de segment                 :  117,94 K

Taille du fichier descripteur d’enregistrement                  :  544,00 K

Pourcentage de fichier descripteur d’enregistrement perdu     :    1,56 %

Total du surcoût d’index                         :  661,94 K

Remarquez comment la valeur du descripteur Mots par descripteur de segment a diminué pour refléter le nombre inférieur d'atomes par enregistrement. La taille du fichier du Descripteur de segment a également diminué. En utilisant texconf vous pouvez déterminer l'impact sur la taille des fichiers d'index lorsque les variables de configuration sont ajustées.